package com.lcy.algorithm.huawei;

import java.util.Scanner;

/**
 * 题目描述:“吃货” 和"馋嘴”两人到披萨店点了一份铁盘(圆形)披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数扇形小块。但是粗心服务员将披萨切成了每块大
 * 小都完全不同奇数块,且肉眼能分辨出大小。
 * 由于两人都想吃到最多的披萨,他们商量了一个他们认为公平的分法:从"吃货”开始，轮流取披萨。除了第一块披萨可以任意选取以外,其他都必须从缺口开
 * 始选
 * 他俩选披萨的思路不同。“馋嘴” 每次都会选最大块的披萨，而且"吃货”知道"馋嘴”的想法。
 * 已知披萨小块的数量以及每块的大小,求"吃货”能分得的最大的披萨大小的总和。
 * 输入描述:第1行为一个正整数奇数N ,表示披萨小块数量。3 <=N < 500。
 * 接下来的第2行到第N+1行(共N行) , 每行为一个正整数,表示第i块披萨的大小。1 <=i<= N。披萨小块从某一块开始，按照一个方向依次顺序编号为
 * 1~N。每块披萨的大小范围为[1, 2147483647]。
 * 输出描述: "吃货” 能分得的最大的披萨大小的总和。
 * 示例1
 * 输入:
 * 5
 * 8
 * 2
 * 10
 * 5
 * 7
 * 输出:19
 * 说明:此例子中,有5块披萨。每块大小依次为8、2、10、5、7。按照如下顺序拿披萨,可以使"吃货”拿到最多披萨:
 * 1、"吃货” 拿大小为10的披萨
 * 2、”馋嘴” 拿大小为5的披萨
 * 3、"吃货” 拿大小为7的披萨
 * 4、"馋嘴” 拿大小为8的披萨
 * 5、"吃货” 拿大小为2的披萨
 * 至此，披萨瓜分完毕，"吃货” 拿到的披萨总大小为10+7+2=19.
 * 可能存在多种拿法,以上只是其中-一种。
 * <p>
 * 注意：排序就错了，这道题不能排序，否则pizza位置就变了
 * 不一定先拿最大的最终结果就大，还是得挨个遍历
 */
public class 分披萨 {
    static int[] pizza;
    // 缓存
    static long[][] cache;
    public static int count = 0;
    public static void main(String[] args) {
//        我自己做的方式();
        标准答案();
    }

    private static void 我自己做的方式() {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] pizza = new int[N];
        for (int i = 0; i < N; i++) {
            pizza[i] = scanner.nextInt();
        }

        //用缓存来记录重复出现过的缺口,可以将递归次数大幅降低（该案例可以从30减到21）
        int[][] cache = new int[N][N];

        int max = 0;
        for (int i = 0; i < N; i++) {//第一层for循环，表示拿的第一块pizza位置
            //缺口至始自终只有1个
            //馋嘴只有一种拿法，只拿最大
            //吃货每次都有两种拿法（不一定拿最大的最终会最大，有可能先拿小的，后面才会出现更大的。因此需要遍历所有情况
            //只能使用递归的思想消耗完数组
            int sum = pizza[i] + getSum(i-1, i+1, pizza, false,cache);
            max = max > sum ? max : sum;
        }
        System.out.println("吃货能获得pizza为:"+max+",递归次数:"+count);
        System.out.println(max);
    }


    private static int getSum(int left, int right, int[] pizza, boolean isChiHuo, int[][] cache) {
        count ++;
        if (right + 1 > pizza.length) {
            right = 0;
        }
        if (left < 0) {
            left = pizza.length - 1;
        }
        if(cache[left][right] > 0){
            return cache[left][right];
        }
        if (right == left) {
            if(isChiHuo){
//                System.out.println("吃货拿到的披萨大小是:"+pizza[left]);
                cache[left][right] = pizza[left];
                return pizza[right];
            }
            return 0;
        }
        int sum = 0;
        if (isChiHuo) {
            //吃货需要尝试从缺口两边找到最大的值返回
            int leftSum = getSum(left - 1, right, pizza, !isChiHuo,cache);
            int rightSum = getSum(left, right + 1, pizza, !isChiHuo,cache);
            if(leftSum > rightSum){
                sum = leftSum + pizza[left];
            }else{
                sum = rightSum + pizza[right];
            }
        } else {
            //馋嘴的值不进行累加
            if (pizza[left] > pizza[right]) {
                sum += getSum(left-1, right, pizza, !isChiHuo,cache);
            } else {
                sum += getSum(left, right+1, pizza, !isChiHuo,cache);
            }
        }
        cache[left][right] = sum;
        return sum;
    }


    /**
     * 递归次数比我写的还要小，为11次
     * 思想是，轮到"馋嘴"拿的时候，不进入递归，直接跳到下一个位置继续计算“吃货”的
     */
    public static void 标准答案() {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        // 缓存
        cache = new long[n][n];
        pizza = new int[n];
        for (int i = 0; i < n; i++) {
            pizza[i] = sc.nextInt();
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, recursive(check(i - 1), check(i + 1)) + pizza[i]);
        }

        System.out.println(ans);
        System.out.println(count);
    }

    /**
     *  进入递归前，"吃货"已经拿了披萨，因此进入递归后，轮到"馋嘴"拿。
     *  "馋嘴"拿披萨的策略固定是：缺口左右两边中较大的那块
     *  而如果"馋嘴"拿的时候，我们不关心馋嘴那块披萨的大小，直接跳过一格继续计算"吃货"的
     *  注意披萨大小各不相同，因此要么左边大，要么右边大，不存在相等的情况
     * @param l
     * @param r
     * @return
     */
    public static long recursive(int l, int r) {
        count++;
        //跳过馋嘴拿的披萨，可以减小递归次数
        if (pizza[l] > pizza[r]) {
            // 拿走第 l 块，因此缺口左边的位置变为 l - 1
            l = check(l - 1);
        } else {
            // 拿走第 r 块，因此缺口右边的位置变为 r + 1
            r = check(r + 1);
        }

        // 缓存优化，如果对应缺口状态的披萨铁盘结果已经算过了，则无需再次重复递归
        if (cache[l][r] > 0) {
            return cache[l][r];
        }

        if (l == r) {
            // 缓存对应缺口状态下，吃货可得的最大披萨大小
            cache[l][r] = pizza[l];
        } else {
            // 缓存对应缺口状态下，吃货可得的最大披萨大小
            cache[l][r] =
                    Math.max(recursive(check(l - 1), r) + pizza[l], recursive(l, check(r + 1)) + pizza[r]);
        }

        return cache[l][r];
    }

    public static int check(int idx) {
        if (idx < 0) {
            idx = pizza.length - 1;
        } else if (idx >= pizza.length) {
            idx = 0;
        }

        return idx;
    }
}
